package subject.lianbiao;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 */
public class isPalindrome {
    public static void main(String[] args) {
//        List<Integer> list = new ArrayList<>();
//
//        ListNode head = new ListNode(1);
//
//        ListNode curr = head;
//        // 将链表拷贝到列表
//        while (curr!=null){
//            list.add(curr.val);
//            curr = curr.next;
//        }
//
//        // 判断回文
//        boolean result = true;
//
//        int left = 0;
//        int right = list.size() - 1;
//        while (left < right){
//            if(!list.get(left).equals(list.get(right))){
//                result = false;
//            }
//            left = left + 1;
//            right = right - 1;
//        }
//        System.out.println(result);

        // 1.找到中间节点，反转后半部分
        ListNode head = new ListNode(1);
        if(head == null){
            System.out.println("");
        }
        ListNode middle = middle_node(head);
        ListNode reverse1 = reverse(middle.next);
        // 2.前半部分与后半部分比较
        ListNode p1 = head;
        ListNode p2 = reverse1;
        boolean result = true;

        while (p1!=null && result){
            if(p1.val!=p2.val){
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        // 3.复原链表
        ListNode reverse2 = reverse(reverse1);
        middle.next = reverse2;
        System.out.println(result);
    }

    // 找到中间节点
    public static ListNode middle_node (ListNode head){
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode p = head;
        while (p!=null){
            ListNode q = p.next;
            p.next = pre;
            pre = p;
            p = q;
        }
        return pre;
    }
}
